import pygame
import random

WIDTH = 800
HEIGHT = 800

PADDING = 40
GRID_WIDTH = (WIDTH - 40 * 2) // 3
GRID_HEIGHT = (HEIGHT - 40 * 2) // 3

GREY = (192, 192, 192)
BLACK = (0, 0, 0)
BLUE = (32, 32, 224)

def to_number(state):
    base = 1
    order = 1
    sum = 0
    for i in range(7, -1, -1):
        # 数一下后面有多少比我小的
        count = 0
        for j in range(i + 1, 9):
            if (state[j] < state[i]):
                count += 1

        sum += base * count
        order += 1
        base *= order

    return sum

def to_state(num):
    state = [0 for i in range(9)]
    order = 1
    middle = [0,]
    for i in range(2, 10):
        t = num % i
        middle.insert(0, t)
        num //= i

    for j in range(9):
        for i in range(9):
            if middle[i] > 0:
                middle[i] -= 1
            elif middle[i] == 0:
                middle[i] = -1
                state[i] = j
                break

    return state

def move_right(state):
    pos = state.index(0)
    if pos % 3 == 0:
        return state

    next = []
    for i in state:
        next.append(i)

    tpos = pos - 1
    next[pos] = next[tpos]
    next[tpos] = 0

    return next

def move_left(state):
    pos = state.index(0)
    if pos % 3 == 2:
        return state

    next = []
    for i in state:
        next.append(i)

    tpos = pos + 1
    next[pos] = next[tpos]
    next[tpos] = 0

    return next

def move_up(state):
    pos = state.index(0)
    if pos // 3 == 2:
        return state

    next = []
    for i in state:
        next.append(i)

    tpos = pos + 3
    next[pos] = next[tpos]
    next[tpos] = 0

    return next

def move_down(state):
    pos = state.index(0)
    if pos // 3 == 0:
        return state

    next = []
    for i in state:
        next.append(i)

    tpos = pos - 3
    next[pos] = next[tpos]
    next[tpos] = 0

    return next

class Solver(object):
    def __init__(self, state):
        self.num = to_number(state)
        self.visited = [0 for i in range(362879)]
        self.queue = []

    def bfs(self):
        self.visited[self.num] = 1
        self.queue.append(self.num)

        while (self.queue):
            a = self.queue[0]
            if a == to_number([1, 2, 3, 4, 5, 6, 7, 8, 0]):
                print("OK")
                return

            self.queue.remove(a)

            state = to_state(a)
            next = move_left(state)
            nexta = to_number(next)

            if (self.visited[nexta] == 0):
                self.visited[nexta] = 1
                self.queue.append(nexta)

            next = move_right(state)
            nexta = to_number(next)

            if (self.visited[nexta] == 0):
                self.visited[nexta] = 1
                self.queue.append(nexta)

            next = move_up(state)
            nexta = to_number(next)

            if (self.visited[nexta] == 0):
                self.visited[nexta] = 1
                self.queue.append(nexta)
        
            next = move_down(state)
            nexta = to_number(next)

            if (self.visited[nexta] == 0):
                self.visited[nexta] = 1
                self.queue.append(nexta)
        
        print("No Answer")

# 棋盘状态
class ChessBoard(object):
    def __init__(self):
        #self.state = ["8", "0", "3", "4", "5", "6", "7", "1", "2"]
        self.state = to_state(random.randint(0, 362880))
        Solver(self.state).bfs()
        self.pos = self.state.index(0)

    def move_right(self):
        if (self.pos % 3 == 0):
            return

        tpos = self.pos - 1
        self.state[self.pos] = self.state[tpos]
        self.state[tpos] = 0

        self.pos = tpos

        draw()
        
    def move_left(self):
        if (self.pos % 3 == 2):
            return

        tpos = self.pos + 1
        self.state[self.pos] = self.state[tpos]
        self.state[tpos] = 0

        self.pos = tpos

        draw()
        
    def move_up(self):
        if (self.pos // 3 == 2):
            return

        tpos = self.pos + 3
        self.state[self.pos] = self.state[tpos]
        self.state[tpos] = 0

        self.pos = tpos

        draw()
        
    def move_down(self):
        if (self.pos // 3 == 0):
            return

        tpos = self.pos - 3
        self.state[self.pos] = self.state[tpos]
        self.state[tpos] = 0

        self.pos = tpos

        draw()
        

pygame.init()

# 创建屏幕
screen = pygame.display.set_mode((WIDTH, HEIGHT))

# 创建棋盘
board = ChessBoard()

def draw_text(font, msg, row, line):
    text = font.render(msg, True, BLUE)
    x, y = font.size(msg)
    screen.blit(text, 
        (PADDING + GRID_WIDTH // 2 - x // 2 + line * GRID_WIDTH, 
         PADDING + GRID_HEIGHT // 2 - y // 2 + row * GRID_HEIGHT))

def draw():
    screen.fill(GREY)
    for i in range(4):
        pygame.draw.line(screen, BLACK, 
            (PADDING, PADDING + i * GRID_HEIGHT), 
            (WIDTH - PADDING, PADDING + i * GRID_HEIGHT), 2)

    for i in range(4):
        pygame.draw.line(screen, BLACK, 
            (PADDING + i * GRID_WIDTH, PADDING),
            (PADDING + i * GRID_WIDTH, WIDTH - PADDING), 2)

    font = pygame.font.SysFont("arial", 200)
    
    for i in range(9):
        t = board.state[i]
        if (t == 0):
            continue

        draw_text(font, str(t), i // 3, i % 3)

    pygame.display.update()

draw()

going = True

while going:
    for evt in pygame.event.get():
        if evt.type == pygame.QUIT:
            going = False
        elif evt.type == pygame.KEYDOWN:
            if evt.key == pygame.K_RIGHT:
                board.move_right()
            elif evt.key == pygame.K_LEFT:
                board.move_left()
            elif evt.key == pygame.K_UP:
                board.move_up()
            elif evt.key == pygame.K_DOWN:
                board.move_down()
